蒟蒻的UR补全计划
写在前面：本篇只是自己看的，所以本来不打算公开，但是最近发现自己效率越来越差（可能是因为UR的题越往后越难），所以放出来希望起到督促自己的作用。本篇题解错误百出
UPD:最后还是剩了一堆坑。
蒟蒻为了变强，效仿吉司机开坑写UR辣！本篇用于记录和写题解。
UR #1：
T1:缩进优化
看数据范围10^6，值域也是，那么考虑枚举每一个x计算贡献。
如何计算？先排好序，设枚举到x，每隔x分一段，在某一段内的元素的floor(a/x)的值相等，剩余部分也很好计算，所以就这样直接计算就行了。
复杂度O(nlnn).
T2:外星人
由于一个数最多被膜log次，所以爆搜在哪里膜了复杂度为C(n,logx),这样问题转化成了：再某些地方取膜的方案数，在确定了取膜的数是谁及其下标后，就知道哪些数必须出现在他们后面，问题就成了：给定一些类似于"一些数必须出现在某个数后面"的排列数，这个用组合数可以计算。
注意:在一个地方取膜的话，必须出现在他后面的数是所有可以让当前数被膜的数。这样用从后往前考虑，用隔板法即可。
复杂度O( C(n,logx) )，看似30分，但由于跑不满，可以得到60分。
突然又想到了如何做第一问，得到了76分。
我们倒着考虑，遇到一个数，可能被膜可能不被膜，如果被膜了那么若膜后为y,则膜前应为y+k*p,所以考虑使用bitset大力表示可能的数字，然后模拟最后看x是否可以被表示出来，即可判断我们一开始定义的值能否被膜出。同时可以二分答案，设二分mid,则判断mid到a[1]-1是否可以被表示出来即可。这样做复杂度O(n*lnn*loga1*x/32)，其实不二分答案也可以利用小常数得到这个部分分。
标解：
感觉自己是个zz,明明已经倒着考虑并且想好组合数怎么转移了，为什么不写个DP？
不过状态定义貌似很神，定义f[i]表示当前为i已经考虑了a[j]<=i的元素,对于两问,分别用f[]表示最终膜出来的数,g[]表示
倒着dp:初始化f[i=(0~a[1]-1)]=i,g[i]=1;
f[i]=max{f[i%a[j]]},g[i]=sum{g[i%a[j]]*S(cnt[i]-1,cnt[i%a[j]])|f[i]=f[i%a[j]]};别忘了比m大的a[j];
T3:跳蚤国王下江南
从来没写过仙人掌，所以不太会写，不知道怎么实现O(n^2)的50分做法。。
做法是:写一下Tarjan然后对于dfn[rt]<low[to]的to说明to是rt连出去的点或者环上的下一个点，直接dp转移即可。
对于反向边，一定满足dfn[rt]<dfn[to]&&pree[to]^i，这时就在这个简单环上转移一下就行了。
注意由于有重边，所以不能用fa判fa边，要单独存储一下。判的时候to^fa变成了(i^1)^pree[rt];
UER #1：
T1:猜数
第一问最大值为2*sqrt(n)=2*sqrt(g*l)=2*sqrt(l/g)*g,第二问最小值为g+l;
只能说：不强转成ll即使乘2ll由于double精度更高所以类型还是double!
T2:跳蚤OS
一道恶心字符串，细节不少挺坑的，其他没什么。
T3: DZY Loves Graph
边权递增且删除的边为前k大的边，所以一条边如果在加入时不是树边，则一直不是，如果在加入时是树边，则直到被删除都是，然后可持久化并查集也可以支持撤销操作。。然后就M了，只有30分。。怎么办啊！？
看了题解后发现自己又是放过了正解。。我已经记录过使用now条边时的状态（连通块数和边权和），加入没有撤销，直接并查集按秩合并（不路径压缩）的复杂度为nlogn的，如果有撤销，由于只会撤销上一个操作，若撤销加边操作，直接当成删边即可。若撤销删边操作，那么我们直接用加入now-k条边时的状态输出本次答案，然后就不删边了！！
注意：在删除时别忘了维护根的sz，注意是根的sz，不是父亲的！
UR #2:
T1：猪猪侠再战括号序列
猜性质觉得每次找右边第一个左括号交换即可，结果真的是这样。。不过题解给的方法更好处理一点：让最终括号序列一定为前半全是左括号，并且使得步数一定是n/2,那么直接单调的两个变量找即可。
T2：跳蚤公路
这个题似乎没什么部分分，所以猜个结论。
二分为0环的上下边界？这样是不行的?我们设一个环上k和为k，w和为b,则k*x+b<0,发现可以二分？不不不，这只是一个环的情形，有很多环。。总不能对所有环去二分吧。。
我们把所有的环归纳起来，bellman-ford实际上f[v][i]表示从1出发走不超过v步到达i的最小距离。我们再加一维[k]表示所有的k和为k的最小距离。因为若是没有负环的话一定走不超过n-1步，所以f[n-1][i]=f[n][i],所以当f[n][i]<f[n-1][i]时说明出现了负环。
接下来我们要求min{kx+f[n][i][k]}>=min{jx+f[n-1][i][j]}(这样没有负环),所以对于所有的k都有kx+f[n][i][k]>=min{jx+f[n-1][i][j]},即求每个k的到x范围的交集。对于固定的k，存在一个j有kx+f[n][i][k]>=jx+f[n-1][i][j],此时是求并集。
在求解出每个i对应范围后，更新一下先走到i，再走到另外一个节点j，j的x的范围即可，仍应该求交集。
注意：负数的向下取整有毒！！-10/3=-3!!
太恶心了，就没写，粘的黄学长的代码。。
T3：树上GCD
30分：由于树高期望为log，所以可以直接维护从一个子树中到根距离为d的点的个数,统计答案时枚举一下，O(nlogn^2)
40分：是由1连出若干链，对于一条链上的，设链长L，则ans[L]+=1,ans[L-1]+=2,ans[L-2]+=3...这个统计可以做到O(n),但是这样做很难处理不同链上的。
我们设f[i]=sum{ans[T]|T%i==0},那么统计f[i]在链内总复杂度是nln的，对于链与链之间,设x[i][d]=L[i]/d,f[i]=sum{x[a][i]*x[b][i]},这里用到一个数学式子:(x1+x2+..+xn)^2=x1^2+x2^2+..xn^2+2*sum{x[i*xj},这样分别维护每一个链的x[d]的和与平方和即可在链内统计的同时完成这一统计，总复杂度O(nlnn);
哈哈哈！我又zz了！！求sum{x[i]*x[j]}直接维护前缀和每次res+=sum*xi,sum+=xi不就行了？！
100分：只能说分块大法好啊！对于30分的暴力合并，这里仍使用容斥的办法。
可以这样做:对于d<=sqrt(n)部分的贡献，我们维护深度为d倍数的数组，可以暴力合并，复杂度O(nsqrt(n))
对于d>sqrt(n)部分的贡献，我们启发式合并维护深度为d的数组，只有两个数组深度L都大于sqrt(n)时才需要处理计算，由于这样的数组不超过sqrt(n)个，所以加上启发式合并复杂度为O(nsqrt(n)log(n)).
PS: VFK的代码太好了！！其中的实现的细节太值得学习了！！下面罗列一下：
1、利用本题fa[i]<i，所以具有天然的拓扑序从底到上处理。
2、枚举d，维护所有人的f[d]，是的空间复杂度降到O(n)（好吧如果vector不clear的话还是nlogn的）
3、在d<=sqrt(n)部分，由于是倒序维护的，所以相当于一个完全背包的过程，直接省去了一个ln(n)//是ln(n)是因为得要枚举L
4、一条链上两个点的贡献直接用40分中的O(n)维护做掉，这样正好使得1没有贡献了，方便在d<=sqrt(n)中跳的时候设立一个边界。
5、启发式合并使用vector的swap,data函数非常简洁。
6、使用vector时push_back()导致是倒着存的，所以用size-i存距离自己为i-1的，同时是距离父亲i的，非常方便。
7、最后的容斥过程也不用求mu，直接倒序用之前已经容斥过的，这样就不用反演就把n^2降到了nln,值得注意的是，这是适用于单组询问的，对于多组询问的还是要反演。
8、这里由于>sqrt(n)的比较少，所以可以设小一点以增快前面的速度。由于一些奥妙重重的原因把sqrt(n)设成11左右似乎是最快的。
对于策爷的解法暂时未看懂，待填。
UR #3:
T1:核聚变反应强度
首先看出sgcd(x,y)=gcd(x,y)/最小公共质因子,差点误入歧途，居然想到使用分解因数的方法。//话说我已经不会Miller_Rabin了？找时间复习一下
然后我就想到答案一定是a1的因数，哈哈哈因数有log个！！
交上去发现爆我存因数的数组了？！发现原来质因数有log个，因数则有sqrt(n)个。。。内心绝望，居然有90分。。
然后我就去看题解，发现：我只存质因数不就行了？！我真是个大zz。。
T2:铀仓库
这个题看到就去想退火，结果退了50分，看来退火不是万能的。然后对着数据调了调参数得了60分。
然后写一写部分分：对于ai=1的每个点都无差别了，我们猜测此时答案在某一个点上，然后扫描线扫我们的序列，用线段树维护距离。然后对于一个点，我们三分左边花多少时间，然后二分求出两边的贡献，更新答案。于是发现对于ai!=1的也可以使用带权线段树来维护，时间复杂度O(nlog2n^2log1.5n).显然会T，可以把二分直接搞在线段树上以此减少一个log或者不用线段树维护了，直接静态使用前缀和后缀和即可。时间复杂度O(nlog1.5nlog2n).对于xi=i的此结论一定成立，对于其他的...就不会证明了，但是配合退火应该有不少分。
看了题解开头后发现这个结论是一定成立的，这样看来我的算法就能AC了，哈哈哈！看来猜结论还是很重要的！
看完题解后发现自己太naive了！首先三分完全不需要，可以二分最远到哪里，然后二分计算出需要时间以判断可行性，时间复杂度O(nlog2n^2)
更优秀的做法是，由于每次选取的一定是连续一段的[l,r],所以从左到右枚举s时，假如我们选定的个数固定，那么l,r是单增的，所以考虑二分答案，当个数确定了，就可以模拟解决，有解的条件是存在一个符合的，复杂度O(nlogn)
T3：链式反应
啊，好难啊！！只会10分状压啊！！
好吧，我果然太naive，想到了是一种奇怪的“树”的组合数DP，但是不会定义状态，更加不会转移。定义f[i]为i个节点的答案，f[1]=1.对于n，枚举儿子的子树大小，剩下的就是被根死光打死的，而对于儿子的子树内则可以重标号统计答案，因为两个子树可以交换，所以f[i]=sum{C(i-1,j)*f[j]*C(i-1-j,k)*f[k]}/2。O(n^3)
接下来自己想如何优化：f[i]=sum{(i-1)!/(i-1-j-k)!*f[j]/j!*f[k]/k!},设g[i]=sum{f[j]/j!*f[i-j]*(i-j)!}就可以辅助求f了,O(n^2),此时发现有卷积！！每次卷一卷就可以倍增一倍，然后递推算出来新得到的f[]数组，继续卷积，复杂度O(nlogn^2),卡常可过。FFT时别忘了“死光攻击”的限制。卡常姿势：将一定需要卷在一起的直接乘在一起，将FFT次数从6降到4.
正解O(nlogn)，但是需要积分，待填。
UR #4:
T1：元旦三侠的游戏
居然是codeforces39E原题，有点小失望。。
T2：元旦激光炮
60分先二分答案，再二分判定很容易。考虑100分做法，由于值域比较大，二分起来没前途，考虑二分每个数组取多少个数，先确定一个，另一个再二分一波就可以判定了，由于第一次二分将值域变小，所以猜测复杂度不是log^2的，得分未知。
对于其中一个数组为空的，可以直接二分一个数组长度，得到另一个数组长度后，比大小，设a[i]<b[i]则a[i+1]>=b[i]为成功条件。
标解做法脑洞比我好到不知哪里去了。首先取l=k/3,设al<bl<cl则比al小的不超过3l-2个数，那么把a1~al都去掉就行了，这样每次去k/3，到k==2时暴力6个即可，复杂度log1.5K+6<=100.
T3:追击圣诞老人
啊啊啊！！我太naive了！！我会的k-短路只有20分！！复杂度O(n*klogn*k).
首先，一个简单而又优秀的优化是：对于每个点能连到的点，我们按照权排序后采用“左儿子右兄弟”的办法这样相当于费用流的“凸费用流”，却保证了堆中只有n+k个元素，只有排序，我们大可不必排序，直接按照点权顺序扫描并判断是否能连边即可，复杂度O(n^2+klog(n+k))，可以获得40分。具体一点的实践为：开一个n^2的数组，表示从rt出发第i小的son，对于从堆中取出来一个(from,rt,v)放入(from,ne[from][rt],v+w[ne[from][rt]]),和(rt,lc[rt],v+w[lc[rt]]).
我们考虑如何优化这个n^2，这里设预处理复杂度为g(n),得到i能到达的点种权值第k小的复杂度为f(n),则刚刚的复杂度写成O(g(n)+k*f(n)loh(n+k))，这里g(n)=n^2,f(n)=1,考虑平衡一下g(n)和f(n),用主席树维护i到根路径的权值线段树，然后对于三个点形成树链的并，可以拆成三条链，做法：两两求lca，有两个相同，在另一个拆开就行了。这样的话三段主席树一起二分，就可以做到g(n)=nlogn,f(n)=logn了，复杂度O(nlogn+klognlog(n+k)),可以得到80分。
我们换一种方式考虑如何把n^2优化一下：实际上我们的链表起到了一个堆的作用，所以我们可以搞一个堆，但是这样是n^2logn的，所以要预处理和可持久化。即倍增预处理出倍增堆。注意：可持久化的可并堆每次取堆首后如果合并的话会多占内存，所以更好的做法是：直接把左右儿子压入堆中，这样可得60,否则炸内存只有50.复杂度O(nlog^2+klog(n+k)).值得注意的是：这里用指针会比下标方便，比直接复制快和省内存。但值得注意的是：这里我们的左偏树任何一个指针指向的量都没进行修改，所以可以在一个为空的时候返回另一个的指针，否则就得返回一个新的。
考虑我们左偏树的作用：找到一个区域内的权值最小的点。我们可以把区域拆成三条链，那么可以这样：把堆中的左偏树换成一条链，每次取出这条链的最小值并拆成两条新的链即可，复杂度O(nlogn+k(log(n+k)+logn^2)),由于树剖常数小，可以过。注意如果把树剖+线段树换成倍增或者LCT都可以少一个log，但是倍增爆内存，LCT由于常数比树剖还慢，所以树剖大法好！
注意：
1、拆链时要注意三点一条链时可能会拆下一个空集。
2、用60分做法中为了方便stq[0][i]存的是自己，这样就与st[j][i]表示含义不同步了。
3、用树剖求y是x哪一个子树的代码：
int k;
while(top[y]^top[x])k=top[y],y=fa[k];
return x==y?k:son[x];
UR #5:
T1:怎样提高智商
额。。纯纯的脑筋急转弯，我猜答案都是4*3^(n-1),方案都输出A 0 0 0 0结果真的是这样的。。
T2：怎样更有力气
这个题的关键在于修出来的路不一定和原有的树一样。首先无论如何肯定修出来是一棵树，其次对于没有限制的，完全可以按照原图纸修，因为每次修路等价于把ui到vi路径上的点连在一起，所以用先按w将天排个序，之后每次把u到v没修的都修上就行了，用树剖+线段树维护O(nlogn^2),可以得到30分。对于一开始的10分。则可以暴力枚举两两之间是否已经连在一起，然后连边，复杂度O(mn^2),可以得到10分，加在一起就是40分了。
事实证明又是我naive了！由于实际就是求覆盖一条树边的最小权值，所以使用树上差分+堆可以做到O(nlogn).
看了题解后，感觉vfk的做法真是秒啊！
我们用两个并查集分别维护：A：同一个联通块内的点，B:在同一个联通块内且在树上相邻的点。然后我们从小到大枚举权值时，对于一条路径可以采取跳B块的方式，这样我们就可以复杂度有保证的取出所有可以连在一起的联通块。然后我们两两枚举联通块，判断能否连边，能的话联通块数--，不能的话组织我们连边的限制--，这样枚举的复杂度是O(n)的。怎样快速判断两个联通块能否连边？只需要判断是否被禁的边数==两个联通块在链上的点数的乘积即可。因为在链上不相邻的联通块需要合并，所以需要一个排序操作，是的复杂度为O(nlogn+n*并查集）。
Vfk的代码也是一如既往的优秀！我们来分析一下代码小技巧：
1、第二并查集在查询时“自动维护”，是将普通并查集拓展出来的，且自动保留了深度顺序，在以后获得某一段有多少个点时提供了方便。
2、论如何在不需要dfn序的情况下一遍dfs或者不用dfs完成树剖的预处理。
3、论如何反复利用数组空间。
4、在lower_bound取得指针时不必转成下标，可以直接用。
吉司机的做法没看懂，待填。
T3:怎样跑得更快
什么鬼啊！？完全想不出离开n^3高斯消元的做法，只有20分！！
对于n<=100的，可以先n^3消除逆矩阵，然后询问时可以用一个n*1的矩阵乘一个n*n的矩阵，复杂度就变成O(n^3+qn^2)了，可以得到40分。卡常真的有65分！！看来以后消元一定得要卡常才行。
这道题的正解思路是一层层的回带，但是假如不忘这个方向去化简的话根本看不出来可以这样搞，所以说这道题脑冻太大了！！以及，这道题还大大加深了我对于莫比乌斯反演的理解，不过这里不筛mu的反演是支持单组询问的，如果询问很多，那么还得筛，并做到预处理O(n)，单次O(sqrt(n))，这里单次O(nlnn)就够用了。值得一提的是，这里的nlnn可以用线性筛做到O(n)，但是对于f[n]=sum{mu[T]*F[T/n]}则难以线性筛。
$$开始时\sum_{j=1}^ngcd(i,j)^c*lcm(i,j)^d*x_j\equiv b_i\pmod p$$
$$由于lcm(i,j)=i*j/gcd(i,j),$$
$$所以可以化成\sum_{j=1}^ngcd(i,j)^{c-d}*i^d*j^d*x_j\equiv b_i.\pmod p$$
$$不妨设f(n)=n^{c-d},假设存在一个F(n)满足f(n)=\sum_{d|n}F(d)$$
$$那么由反演可得F(n)=\sum_{d|n}f(d),$$
$$但也可以直接由之前的式子得到F(n)=f(n)-\sum_{d|n且d\neq n}F(d) $$
$$由这个式子可以直接容斥，代码如下(复杂度O(n\ln n))$$
for(int i=1;i<=n;i++)F[i]=f[i];
for(int i=1;i<=n;i++)
for(int j=i+i;j<=n;j+=i)F[j]-=F[i];
$$现在我们的式子变成了\sum_{j=1}^n\sum_{d|gcd(i,j)}F(d)*i^d*j^d*x_j\equiv b_i.\pmod p$$
$$因为d|gcd(i,j),所以d|i且d|j,所以可以写成$$
$$\sum_{j=1}^n\sum_{d|i且d|j}F(d)*i^d*j^d*x_j\equiv b_i.\pmod p$$
$$先把i提前i^d*\sum_{j=1}^n\sum_{d|i且d|j}F(d)*j^d*x_j\equiv b_i.\pmod p$$
$$再把d提前i^d*\sum_{d|i}F(d)*\sum_{d|j}j^d*x_j\equiv b_i\pmod p$$
$$不妨设g(d)=\sum_{d|j}j^d*x_j$$
$$上式变成了i^d*\sum_{d|i}F(d)*g(d)\equiv b_i\pmod p$$
$$也就是说\sum_{d|i}F(d)*g(d)\equiv b_i/i^d\pmod p$$
$$我们把b_i/i^d看成一个函数b(n),把F(d)*g(d)看成函数B(n), $$
$$则b(n)=\sum_{d|n}B(d),现在我们有了b(n)，当然可以像刚才一样容斥得到B(n) $$
$$现在我们有F(d)*g(d)了,同时又有F(d),自然就有g(d)的值了$$
$$好，现在我们有了g(d)=\sum_{d|j}j^d*x_j,考虑如何解j^d*x_j$$
$$不妨设G(j)=j^d*x_j,那么g(d)=\sum_{d|T}G(T)$$
$$我们当然可以用莫比乌斯反演G(d)=\sum_{d|T}\mu(T)g(T/d)$$
$$但完全可以由刚才式子得到G(d)=g(d)-\sum_{d|T且d\neq T}G(T) $$
$$可以用下面的代码在O(n\ln n)的时间内得到$$
for(int i=1;i<=n;i++)G[i]=g[i];
for(int i=n;i;i--）
for(int j=i+i;j<=n;j+=i)G[i]-=G[j];
$$原来和树上GCD那题的容斥一样呢！！ $$
$$有了j^d*x_j，我们自然可以求x_j是多少了$$
什么时候无解呢？
我们考虑上述过程中哪里用到了除法:
$$1、b_i/i^d，由于i^d一定不是p的倍数，所以没问题$$
$$2、g(d)=B(d)/F(d),这里F(d)可能是P的倍数(感觉糟数据的人好辛苦啊)，此时若B(d)==0,则多解，不妨随便给g(d)赋个值$$
$$x_j=G(j)/j^d,由于j^d一定不是p的倍数，所以没问题$$
手动给出题人点赞！妙啊！
UR #6：
T1：破解密码
额...看上去只会n^3的高斯消元，不过因为这是个循环矩阵，肯定有什么奇怪的性质，而且值域这么小应该也有什么搞头的样子？为什么UR的T1都变得这么难了！！
看题解之前先看了别人的程序，为什么大家50分的都写的不是高斯消元？正当我怀疑人生时，看了看题解，50分做法确实是高斯消元，难道只有和我出题人想的一样？然后看了100分做法，发现原来大家都是被没逆元给坑了！果然是我太菜了。。
设A=O_____,B=_____O,那么A*26-B=O*(26^n-1),这样就可以把每一位的O求出来了。但是26^n-1可能没有逆元，此时26^n=1,那么对于一个A=O_____，A*26后O的系数变成了26^n=1,所以A=B=_____O,此时所有的值都相等，直接求一下就行了。更加方便的，这里不用考虑膜掉的情况，因为只要构造出一种使得其值为给定值即可，所以直接瞎xx用除法就行了。
T2:智商锁
首先先zz一发去做矩阵树拿3、4两个点。这时候想要构造1、2两个点，发现：原来这是个分解因数啊！然后分解因数看起来能过掉1257，这样就能有60分了！但是分解完因数后我又zz了！我一直错在如何构造！！最后采取的构造方式是：先铺一条长度为因数个数的链，然后链上每两个点伸出一个环，环上的个数为因数。这样还需要注意由于做不出两个点的环，所以因数不能有2.做到这就做不下去了，因为不知道怎么分解因数了。
看了看题解，我怎么从来都不知道
$$n个点的完全图生成树个数为n^{n-2}$$
有了这个结论就知道第五个点是完全图了，同时，第六个点其实也是！！
可怕，这道题居然是随机化算法！！随机1000张点数为12的图，那么他们生成树个数在12^10内随机分布，然后我们规定要找出4张图使得他们生成树个数的乘积等于K，这一点可以先两两组合预处理出来，然后再枚举+Hash表。（现在的UR的T2都这么变态了。。）
T3:懒癌
纯纯的智商题，懒的想了。。先弃掉，有空再填。。
UR #7:
T1:水题生成器
比较惭愧，没仔细想就写了算法四，即贪心的做法，也没有证明为什么一定能拼出来。看了看题解，反阶乘进位制这个思想非常好，即用n*(n-1)*(n-2)*...*(n-k)作为位，这样表示n!以内的数只需要n位。
T2:水题出题人
挺有意思的了解各种排序的题目，记录一下吧：
猴子排序。每次把数列胡乱地打乱，判定是否有序，直到有序为止。
冒泡排序。重复地走访过要排序的数列，每次比较相邻两个元素，如果它们的顺序错误就把他们交换过来。
选择排序。每次在未排序的部分找到最小的元素放到已排序数列的末尾。
计数排序。使用一个额外的数组 C，其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数，然后将 A 中的元素排到正确的位置。
归并排序。把数列分成左右两部分递归进行排序，然后利用归并操作合并两个有序数组。
快速排序。从数列中挑出一个元素作为基准，接着把比基准小的数放在基准左边，大的放右边，递归左右两边进行排序。
1、卡计数排序放归并排序：把数设大点就行了。然而归并的常数好大，只能n=1.
2、卡选择排序放冒泡排序：两者都是n^2的，所以要卡常数！太难构造了！标解说输出1900个数，有一个是1，让我自己去二分！！最后二分出来为1469。。。
3、卡快速排序放归并排序：因为快速排序是选中间的为基准，所以每次让选的都是最大\最小的就行了，只要每次将最大的放在中间就行了！也就是说
$$for(int\space i=0;i< n;i++)swap(a[i],a[i>>1]);$$
就行了，n还要二分，得出来是1984。
4、卡冒泡排序放计数排序：因为冒泡是n^2的，所以只要让计数排序能过就行了：先从40到11每个扔40个，再从10到0每个扔42个，一共1015个。
5、卡冒泡排序放选择排序：玩不动了，丢～
6、卡快速排序放猴子排序：玩不动了，丢～
T3:水题走四方
哈哈哈哈！在想的时候构造了一个又一个的反例，最后以为自己想到了可能没毛病的O(n)做法，然而一看题解，哈哈哈！没错我构造的那些反例题解都提了，但是我这种做法也出现在了错误范例里！！
我的做法是：定义f[i]为i的最佳答案，cost[i]为从i开始一遍遍往下遍历完i的子树的花费，leaf[i]为i子树中叶子的个数，mxdp[i]为i距离子树中叶子的最大距离，e[i].dis为把一条链缩起来后的边权，然后按照拓扑序转移：f[rt]=min{f[son]-cost[son]-leaf[son]+max(0,mxp[son]-e[i].dis)},表示在rt这里先遍历完除去son以外的子树，然后在最后时刻rt和去其他子树的开始一起往下走，然后在第一个分叉处召唤它。
这样做的反例为：
假如有两根很长很长的筷子，我们把用于吃饭的那一头粘起来并作为根结点。那么答案显然是一根筷子的长度。但是如果这两根筷子是劣质一次性筷子，在两根筷子的侧边长了一点点毛刺，这些毛刺比较靠近吃饭的那一端。那么最优解是什么呢？
最优解是：先派个地卜师下去把毛刺都去掉，然后再两个地卜师一起下去分别遍历两根筷子的主干部分。这样大约就只需要一根筷子的长度。而如果用刚才那个算法，会算出来是大约两根筷子的长度。于是这个算法又是错的。
哈哈哈，姿势不对，活该爆零！（不过出题人也说自己狂对拍才拍出来，真是良心！）
正确姿势：我们考虑主巫师一定是从根走到某一条链，那么中间过程一定是主巫师笔直的从某一个关键点移动到另一个关键点，此间克隆巫师去消灭所有的分枝。这样显然上面那种情况就没有问题了，因为主巫师只要选择了恰当的停的位置，就可以做到最优了。
好，我们重新开始：定义f[i]为从根走到i的最小代价，dp[i]为深度，sumleaf[i]为子树叶子的深度和，cntleaf[i]为子树叶子个数，mx[i]为子树叶子最大深度，smx[i][j]，为出去j这颗子树的子树叶子最大深度,prt为rt的祖先。
f[rt]=min{f[prt]+cost(prt,rt)}；
cost(prt,rt)为从prt走到rt并消灭分枝的最小代价，可以得到
cost(prt,rt)=sumleaf[prt]-sumleaf[rt]-(cntleaf[prt]-cntleaf[rt])*dp[prt]+min(dp[rt]-smx[prt][rt],0);
+min(dp[rt]-smx[prt][rt],0)是什么东西？
考虑克隆巫师走最后一条最长的链时主巫师同时往下走的代价是max(dp[rt],smx[prt][rt])-dp[prt],而smx[prt][rt]-dp[prt]已经包含在之前算得代价里了,又因为max(dp[rt],smx[prt][rt])=smx[prt][rt]+min(dp[rt]-smx[prt][rt],0),所以就是这样：
$$ f[rt]=min\{f[prt]+sumleaf[prt]-sumleaf[rt]-(cntleaf[prt]-cntleaf[rt])*dp[prt]+min(dp[rt]-smx[prt][rt],0)\}$$
这么做复杂度O(n^2)可得50分。
考虑优化：首先smx[][]这个东西可以用线段树或者ST表按照dfs序维护深度，查的时候相当于查一个序列挖掉一段后的最大值，当然可以拆成两半，因为转移复杂度为O(n*查询)所以采用ST表O(nlogn)预处理O(1)查询比较合适。
然后，我们知道对于一条链肯定直接转移就行，对于dp[rt]>smx[prt][rt]的，肯定可以变成：一起走，走到克隆巫师到头了，瞬移过来接着一起走，而克隆巫师走的由于是最长的链，所以瞬移之后的路上一定没有分枝了。那么我们分情况：
$$f[rt]=
\begin{cases}
f[fa[rt]]+1(fa[rt]只有一个儿子)\\
min\{f[prt]+sumleaf[prt]-sumleaf[rt]-(cntleaf[prt]-cntleaf[rt])*dp[prt]\}（smx[prt][rt]>=dp[rt])）,
\end{cases}$$
这样我们就不用维护smx[][]了！
进一步想，我们在从根到rt的这条链上，可能更新的prt一定满足：若dp[prt1]<dp[prt2]则smx[prt1][rt]>smx[prt2][rt].否则一定可以是从prt1转移到prt2再转移到rt，效果等价。所以我们可以只维护满足条件的prt，用一个单调栈存储，而且由于dp[rt]递增，而我们只需要smx[prt][rt]>=dp[rt]的prt，所以在一些情况就不用进栈了，发现假如单调栈添加一个元素，那么一定在其他分枝有一个很长的链，这样的话就保证了单调栈中元素不超过sqrt(n)个，我们转移时扫一遍单调栈是O(sqrt(n))的，在树上执行撤销操作也是O(sqrt(n))的，所以总体复杂度是O(nsqrt(n))的，可以得到80分。
其实，我们在想到了上面那个分情况的转移后由于去掉了取min，所以可以斜率优化了！化简后斜率式子：
$$设dp[i]>dp[j]且从i转移比从j转移优,则$$
$$\frac{(f[i]+sumleaf[i])-(f[j]+sumleaf[j])}{dp[i]-dp[j]} < cntleaf[i]-cntleaf[j]$$
这里x(i)和g(i)都是单调的，可以用购票的方法做，复杂度O(nlogn^2),还是80分。
下面介绍满分做法（终于到满分做法了，感动）：
1、根据上面的证明，顺水推舟的我们发现由于转移是有一个传递关系的，所以每个点只要用它上面那个最近一个出现的smx[prt][rt]>=dp[rt]的prt就行了也就是我们的队尾的元素！那么怎么降低撤销操作的复杂度呢？骗分：弹栈的时候二分一下弹过去，然后记录一下覆盖掉了谁，回头恢复一下，这样就是O(nlog(sqrt(n)))的，而且远远达不到，所以能A.
2、使用长链剖分：每次选择一条最长的链染黑，先走黑链，一路开黑到底，然后回溯，撤的过程中去分支，也就是新的黑链，那么会使得栈变成进入此条黑链前的状态，在那个位置压入黑链并进入新黑链，注意由于之前的黑链一定更长，所以pop不掉旧的黑链。这样的话我们相当于没有撤销操作了！复杂度自然是O(n)的了！
3、我们只是要找到每个点离他最近的smx[prt][rt]>=dp[rt]的prt，记为p[rt],那么我们可以抛弃单调栈的思想：我们按拓扑序倒序合并子树，维护两个信息：还未找到p[rt]的rt（由于只与深度有关，可以存记录下一深度的节点），已有的最长的链，这样把一颗子树与父亲合并时，用父亲已有子树信息更新一下新子树，用新子树更新一下已有子树就行了！复杂度同样是O(n)的！
UR #8:
T1:赴京赶考
精彩操作！果然我弱到连T1都不会做的地步了！不够这个思路一如既往的好啊！
因为每次走一个格子只会横坐标移动或者纵坐标移动，那么我们发现实际上计算代价时两维互不干扰！因为假如从(i,j)走到(i,j+1),费用是0还是1取决于b[j]和b[j+1]是否相同！这样我们只需要把两位分别考虑，预处理前缀和，查询的时候分情况就行了。
T2:决战圆锥曲线
看到了“线段树”的标签也不会写。。跪烂吉司机
先说50分做法：由于c=0,所以是求qx+by的最大值，这个在凸包上，所以线段树每个端点存一个凸包就行。因为数据是随机的，所以凸包大小是log的，那么单点修改直接暴力修改凸包就行，区间取相反数的话同时维护一个下凸包就可以了（感觉并不好写的样子。。）
接下来c！=0时，发现答案并不是凸包上的点，但是发现加入存在x1<=x2&&y1<=y2那么(x1,y1)一定不对答案作贡献，所以维护一个单调栈（随x增大y下降的单调栈），由于数据随机，所以长度是log的（数据随机这个性质好优美啊！）。维护方法类似凸包，也得维护两个。复杂度O(mlog^2)，可以的得到80分。
满分做法画风突变，变成小清新线段树了！
注意到虽然m是10^6能卡掉O(mlog^2),但是询问只有10^5,所以我们加入能把修改的复杂度降下来，保持查询的复杂度，那么就能A了！考虑维护区间y的最大值，这样显然是log修改的。然后考虑查询：设calc（x,y)=ax+by+cxy,对于区间[l,r],若Calc(r,mx[rs[rt]])>ans,则递归，否则返回，然后若Calc(mid,mx[ls[rt]])>ans，则递归，否则返回。这样做由于每次递归时一定是因为出现了一个比之前的y都大的y，（因为x是递减的），由于数据随机（又是数据随机！），所以只有log个这种关键点存在，每次递归最多log层，总体复杂度又是log^2的，这样就能A了！
总结：数据随机奥妙重重。小清新线段树复杂度**。这题的修改操作完全是坑人去写50分、80分那种难写而且与正解关系不大的做法。
T3：宿命多项式
吓跑了。。
UR #9:
T1：电路手动分析
感觉是个细节题，首先二分答案，然后最优的应该是宽为min(sqrt(ans),n),这样最后一行可能剩下几个，然后计算代价：设矩形是L*R+y的，ans*(ans-1)/2-（L*(R-1)+R*(L-1)+y+y-1）,然后和r比较即可。看题解以后确实如此。注意二分上界应为min(n*m,2e9).
T2：App 管理器
理解错题意了，以为是：给混合图定向使得成为一个欧拉回路。首先给无向边随意定向，然后统计每个点的入度-出度，正的连S，负的连T，对于我们随意定向的边u->v,连v->u.输出方案直接看边就行了。
结果是：给混合图定向使之成为一个强联通分量。用上述方法居然得了30分。。
正确做法：首先，因为保证有解，我们可以证明：如果不存在v->u不经过(u,v)这条边的路径，那么一定存在u->v不经过(u,v)这条边的路径。
证明：设v能到的集合为S，不能到的集合为T，那么因为有解，所以v可以先经过u再到达T的每一个点，所以u能到T的每一个点，此时图被分成了S和T两个部分，假如(u,v)这条边是桥，那么无解，所以(u,v)不是桥，所以S和T其实是联通的，与假设矛盾，不成立。所以原命题成立。
那么我们就可以直接暴力dfs做了，复杂度O(m^2).
T3：包子晚宴
又是一个提交答案题，表示练得少，不知道怎么做。
先全都输出S（原地不动），得到了良心的每个点2分。
然后看第一个点，一开始以为半径都为0的话永远不可能中弹，然而并不，写了个暴力使得经过所有的点，依次得到了5分。然后只要一开始走一步到达一个小数点位置就行了。
第二点看起来躲子弹奖励明显高，所以尽量躲子弹，而且每个子弹出现都是一瞬间，所以可以爆搜一下？
写不下去了，弃掉吧，要是NOI考提答，一定不要浪费太多时间在上面！
UR #10：
T1:汉诺塔
这个题想了几种没有通法的做法，然后复杂度不会算。。反正不超过n^2,至少有60分了。
先说下nsqrt(n)做法：每次先暴力拿出最大的100个，然后排序，然后暴力排序，操作数：n/100*(n+100^2)=nsqrt(n).
然后考虑分治：每次当其他两根柱子当空气，然后把小于等于mid的和大于mid的分开放，然后分治下去好了，可以递归的时候先递归右边，这样最后就可以堆在一起了。
T2：世界线
可能是受上一题分块的启发了，一上来想到分块做法，然后就发现想错了。又看到无解的情况发觉自己似乎在naive的沼泽中越陷越深了，T_T
于是又去看题解，感觉这个题妙出个新高度啊！
我们重新考虑分块：我们分好块后就知道谁和谁是一个块内的了，但我们无法区分这些个块，所以我们可以使得块的大小不同，这样就可以区分每一个块了！所以对于n=k*(k+1)/2的，我们先将1到n排在一个k*k的i<=j的三角形区域内，然后先按x连边、查询，再按y连边查询。因为这样做x和y都不同，就可以迅速确定每一个点了。这样做结合暴力做法：构成两种间断的链，但是留着两头的点不连，这样可以判断出两头的点是谁，然后就可以往里推得到所有人。这样共60分。
我们考虑n！=k*(k+1)/2的，我们将剩下的也放在一列里，发现会有两列块大小相等，于是要区分这两列，怎么办呢？我们联系暴力的做法，可以将最后一列的最后一个放在k+1的位置，这样只有最后一列的k+1和倒数第二列的k在横坐标上块大小为1，根据两者在纵向上的块大小就能区分了，于是最后一列和与他纵向上块大小相同的块也和他区分开了。可以得到70分。
但是，当n=k*(k+1)/2-1时，最后一列和倒数第二列大小相同，这时候怎么办呢？我们可以这样搞：把最后一列的第一个放在k+1，这样根据横向块大小为1的只有最后一列有，就可以区分出最后一列和倒数第二列，然后根据有无最后一列的点区分第一行和第二行就可以了。
不过，这样做的询问次数为2*n*sqrt(2n)>10^6，我们考虑"卡常",发现当确定一个点是那个块的时候就不用继续询问了，这样询问数一下子就小了！
什么？怕Hack?不太清楚会不会有人根据这一卡常方式构造数据，不过可以这样：由于一个点属于块的大小比较大的块概率较大，所以每次按已知块大小的顺序询问就行了，这样就不怕被卡了！
果然，代码实践起来还是要精简，自己这道题似乎只会写成分情况的情况，其实可以这样：先统一搞完每一次块，然后看n是否正好等于k*(k+1)/2，如果不等于，那么我们先消去最后一行。对于n=k*(k+1)/2-1的情况，我们不能把最后一个点放在k+1，那么我们可以把整个序列推到右边，即从k+1到着连。最后居然长度和时间双榜1，感人肺腑。
T3：列队
UR的T3真是要命啊！这个还是只会最裸的暴力，复杂度是得不到20分的，不过剪枝之后还是没有问题的。
不会想啊，看了看40分做法：由于B[i,j]≡i+j−1(mod m),所以这是一个循环置换，所以问题等价于求多少个循环置换不同的形态个数为m。设一个置换由K个分别为Ai大小的循环组成，那么它不同形态个数为lcm{Ai},所以可以dp，设f[i][j]为前i个元素不同形态个数为j个方案数，转移时固定i，即规定i在第i个，f[i][j]=sum{f[i-k][a]*C(i-1,k-1)*(k-1)!}，需满足lcm(a,k)==j.边界f[i][1]=1,f[i][i]=(i-1)!,ans=f[n][m].
剩下的太难了，就跑了。
UR #11:
T1：元旦老人与汉诺塔
T1怎么都肿么难！
看了题解以后想想都害怕，吉司机绝壁和分析复杂度有仇！把暴力的状压改成爆搜就能过！就因为实际状态数很少！
好吧，我们这么想：因为操作数有限，所以每根柱子我们实际能动的只不过是最上面几根（因为想动k根柱子需要2^k次操作），而且实际难以达到上限，所以复杂度就是O(跑得过）。
T2：元旦老人与丛林
一个悲伤的小故事：pkusc的R3的F与这个题的子任务2惊人的像，假如我早点刷UR，那么就能A掉那个F了。。
好吧，这个题我还是不会，不过他问题的转化挺神的。我们看子任务：每个点的度数都不小于4，那么这个图m>2n-2,所以一定是No。由此猜想如果整张图不存在一个子图m>2n-2,那么这张图是“丛林”。
证明：
为了方便，我们称m==2n-2的图为”满图“。
我们考虑使用一张满足“不存在一个子图m>2n-2"的图中度数最小的点将这张图拆成两部分，假如可以的话，那么这张图就是一个“丛林”。那么度数最小的点度数<=3,当度数<=2时，可以轻松的拆成了两部分，所以考虑度数==3的情况。
设图为G,设度数最小的点为u,与之相连的点为a,b,c.设将u和其边去除后的图为G1。
使用归纳法证明：首先n=1时一定正确，假设已经证出当点数<n时正确，下面考虑当点数==n时：
先证明两个满图如果相交，那么他们的并是满图。考虑设相交的点数为V0,边数为E0，那么E0=2V0-2,两个图的并中点数为V1+V2-V0,边数为E1+E2-E0，由于均满足E=2V-2,所以并图也是满图。
a,b,c中存在一对x,y满足G1不存在一个子图包含x,y且是满图：假如分别存在3张满图分别包含a,b,c中的两个点，那么他们的并图也是满图，此时把u和连接a,b,c的边加入，得到的还是G的一个子图，但此时E=2V-1与“不存在一个子图m>2n-2”假设矛盾，所以a,b,c中存在一对x,y满足G1不存在一个子图包含x,y且是满图。
那么我们假设找到了x,y，我们可以先在G1中给x,y连边，得到G2仍满足“不存在一个子图m>2n-2”，所以此时G2是一个丛林，且一定能拆成两个森林其中一个包含x,y,我们把边x,y替换成u-x,u-y,那么仍是一颗森林，把另一边加入u和一条边仍然是一个森林，所以我们从u把这张图拆成了两个森林。得证。
证明完了后，我们问题就转化成了：求一个图，是否满足每一个子图都有m<=2n-2.
然后的问题转换才是重头戏（前面的证明也很重要呀）
我们现在要检验这张图是否存在子图满足m>2n-2,不妨给一个点的权值赋为-2,边权赋为1，跑一个最大权闭合子图，如果权>-2，那么就成立，否则不成立。
这样做确是不行的：因为最大权闭合子图权>=0(空图)，怎么办呢？我们枚举一个点，使其权值为0，那么跑最大权闭合子图显然可以包含他，而且此时权>0就能表示m>2n-2了！复杂度O(nmsqrt(n))（二分图），可以得到80分。
剩下的，由于我们发现每次重新跑只有两个点的权值改变，即两条边的容量改变，所以我们只需要搞推流：即把下一次权为0的点当源点，源点当汇点，跑一发，复杂度为2m,所以总体复杂度变成了O(msqrt(n)+nm)就可以过了！
一个常数优化：每次Dinic的Dfs一开始穿进去的v实际上是可能增广最大流量，所以我们可以每次传一个有意义的值Lim，比如第一遍跑的时候传m，之后退流的时候传要退的流量，下一次跑的时候传上一次退掉的流量，每次Dfs时候传Lim-flow。
然而这样仍然过不了，你需要bfs去手动消流，不过加上点奇奇怪怪的trick就可以过了。
T3：元旦老人与数列
哈哈哈，吉司机线段树诞生题？然而学校网吧百度网盘完全禁了，看不了题解，看了看吉司机的代码k1、k2、k3、k4、k5、k6好雷人，吉司机难道不会搞混吗？希望没理解错。
操作：
1、区间加。
2、区间取max。
3、查询区间最小值。
4、查询区间历史最小值。
5、可以加一个区间求和。
首先我们确定一下要维护哪些量：(以下次小均指严格次小)
1、区间最小值mi[]
2、区间历史最小值num[]
3、区间次小值se[]
4、区间最小值增量A[]
5、区间次小值增量B[]
6、区间最小值历史最小增量preA[]
7、区间次小值历史最小增量preB[]
8、区间和sum[](针对区间求和)
9、区间最小值出现次数ti[]（针对区间求和）
接下来说一下每个操作：
1、区间加：直接加，同时维护所有变量。
2、查询区间最小值：直接查，已经维护好了。
3、查询区间历史最小值：直接查，已经维护好了。
4、区间取max：1、若mi[rt]>=qx,则return;2、若se[rt]>qx（注意因为se[]是严格次大值，所以不能取等！）,则直接维护：将操作变成给区间所有等于最小值的元素加一个值，同时维护mi[],A[],B[],preA[]，sum[].3、暴力递归儿子。
5、区间求和：直接求就行了，已经利用ti[]维护好sum[]了。
咋口头AC这么容易呢？
再说一下Updata()和Pushdown()这两个操作：
Updata():
若两个儿子最小值相等，则次小值为二者次小值较小的。
若不等，则最小值为较小的，次小值为最小值较大的最小值和另一个的次小值中较小的。
历史最小值更新为两个儿子历史最小值的较小值。
Pushdown():
首先取两个儿子最小值的较小值now（注意不能直接取父亲的最小值，因为我们是为了得到父亲的最小值和较小值的来源），若一个儿子最小值==now，那么用mi[son]+preA[fa],preA[fa]+A[son],A[son]+A[fa],preB[fa]+B[son],B[fa]+B[son]来更新num[son],preA[son],A[son],preB[son],B[son],否则用mi[son]+preB[fa],preB[fa]+A[son],A[son]+B[fa],preB[fa]+B[son],B[fa]+B[son]来更新。然后正常的给mi[son],se[son]分别加上A[fa],B[fa]或B[fa],B[fa].注意：小心se[son]>inf爆int.(因为有的区间权值都相等,se[son]==inf)
这样就愉快的AC辣！（哈哈哈，居然只写了1.3k就完成了)
UR #12:
T1：实验室外的攻防战
一开始想的是：从数值从大到小考虑，看能不能把数依次放到对应位置，但是很快捏了组反例：（321）->(132)如果先动3的话，2就过不去了，由此想到按照结束后的序列从后往前考虑，看起来没问题了。
现在问题转换成了：每次询问一个数在到达想要位置路上有没有比它大的。这个可以转化成：查询区间最大值+把单点赋值成0.这道题就愉快的结束了。
发现这么做没问题，又看了看榜一做法：按数值从小到大考虑，判断i在A序列位置之前有没有数值比i小的在B序列中的位置比i在B序列中的位置大。这样做的话本质和我做法相同，不过他的从结果角度考虑，我从过程角度考虑，但他可以直接用树状数组代替线段树，就能小常数了。
T2：密码锁
这道题除了19分暴力以外，又想了想m=0的7分，写出来复杂度是n^2的，然后受到启发，写出来一个复杂度3^n*(n+m)的算法，似乎并不能多得分。。然后去看题解，发现自己还是不会利用图的性质。
首先完全图的边定向后为竞赛图，竞赛图满足：将强联通分量缩点后，形成一个链式结构（注意不是树的链），且每一个Scc到身后的Scc都有连边。
这道题我们虽然计算期望可以转化成计数问题，但是正解还是计算期望。我们考虑如何计算竞赛图Scc个数的期望：我们枚举强连通分量的前缀，那么这个图的形态就会被枚举Scc个数次，那么把这个形态的图出现的概率加在一起就是Scc个数的期望了。但是这样做还是需要枚举图的形态，这样是不行的！考虑因为确定了某个前缀后，假如不乘后面的概率，那么就相当于在每一种拥有这个前缀的情况都统计了一遍，这样的话枚举量就可以接受了。我们接下来考虑怎么计算概率：枚举一个前缀应当满足，它和非前缀之间的边一定是由他为起点的。考虑到这样做往这个前缀后面接其他前缀也是对的，所以这个做法是对的了！
剩下的事情就是枚举前缀了：由于一个Scc的出边来自于所有属于这个Scc的点，所以可以枚举Scc中的所有点，所有前缀中的点与非前缀中的点强制定向，这样就可以了，复杂度O(2^n*m),这里m=n*(n-1)/2。
我们再来考虑m=0的做法，套用之前的做法的话我们发现由于每条边正反方向的概率都一样，所以我们不用枚举点集了，状态直接定义为前缀中点的个数，复杂度O(n),结合之前算法可以得到49分。
考虑到上述两个做法区别的原因在于m，即特殊边的数量，而m又很小，所以我们可以枚举边集。像上一个算法一样考虑一个有x个点的前缀，假如这x个点没有与特殊边有关的点的话，贡献为0.5^(x*(n-x)),而假如有一条边且由x发出的概率为P,则贡献变成了0.5(x*(n-x)-1)*P=0.5^(x*(n-x))*2P，从这个角度，我们只要计算出来x个点的前缀的特殊边的贡献之和，乘上0.5^(x*(n-x))就行了。首先枚举边集，之后进行黑白染色，这样会形成一些联通块，每个联通块都有两种情况，每种情况的贡献都很好计算，然后做一个分组背包就可以了，复杂度O(2^m*n^2)可以得到73分。
最后我们发现由特殊边形成的联通块是互不干扰的！我们可以枚举这些联通块中选择哪些点，计算出贡献来，然后再做背包的DP，就可以做到O(2^(m+1)*n+n^2)了，这个题就能A了！
T3：a^-1 + b problem
蒟蒻不会多项式除法啊！(跑...
UR #13:
T1:Yist
一开始zz了，觉得因为有的点不需要比大小，所以需要写颗线段树，实际上不需要的，直接把链表赋成身边第一个需要比大小的就行了。具体一点：若答案x成立，那么必须满足每个要删除的点管理的最小值范围-范围内比它大的数（一定是被删的，但被删的不一定是）的个数（不和其他需要删除的点比较）>=x，这里实际上可以直接减去区间内被删的点，因为如果存在被删的点比它大，那么它的区间一定更短，所以这个错误的结果不会影响答案（这其实是我一开始没想到，后来突然想到了，但是却能惊喜过样例，然后想了想才给证出来的），所以O(n)链表搞一搞就行了。
被硬生生卡常卡成60。。
然后又分析了一波复杂度，发现是复杂度不对了！（捂脸），因为现在链表的初始值不再是旁边那个人，所以可能会使得原先缩成一个块白缩了更加正确的做法：从小到大加数，用并查集维护加点，复杂度n*并查集。
标算：myy的std真是比这些非线性做法高到不知道哪里去了！从大到小枚举，每次暴力找区间，同时打上访问戳，假如遇到了打戳的，那么就就返回就行了，因为你的区间肯定能包含这个戳来源的那个区间，那么就一定不会更优。
T2：Ernd
感人肺腑，原先一直不太懂为什么“免费馅饼”那题可以转换成二维偏序（没有找到有证明过程的题解），今天终于看到证明了：把一个时间看作(ai,bi)的话，可以发现因为转移要满足|ai-aj|<=bi-bj所以j一定在i的上方45度到135度这个范围内，所以愉快的转坐标系变成(ai-bi,ai+bi)后转移点都在i的左上方，就可以转化成一个二维偏序然后用树状数组搞了。
回到这个题，我们发现转移有两种：
f[i]=max(f[i],f[j]+1|接到第j个水果后可以接到第i个水果)
f[i]=max(f[i],f[j]−1+(i−j+1)^2|第i个水果和第j个水果属于同一段)
对于第一种可以用刚刚说的二维偏序搞，第二种因为权值和i,j有关，所以没法用二维偏序，假如直接转移的话可以得40分（后20来自于答案不超过10000，所以枚举j时i-j+1<=100）
首先，设j<k,发现(i-j+1)^2的增长速度远超(i-k+1)^2的增长速度，那么当j转移比k优时，k再也不会比j优了，所以就有决策单调性了（咦，倒着的决策单调性？）
其他做法：我们发现f[i]=max{f[j]-1+(i-j+1)^2}是一个可以斜率优化的式子，我们把它的转移式化简出来长这个样子：(fj-fk+j^2-k^2)/(j-k)>2(i+1).当j为最优解时T(i,j)<g(x)<T(j,k),这里要维护一个上凸包，由于g(x)递增，所以要删除队尾元素，最优值取在队尾（这不就是个栈吗！？）。实践过程中，由于我们得按照转坐标系后的横坐标顺序转移第一部分，同时转移第二部分，所以为了方便，我们事先将第二部分可以转移的每一段分配一个数组的空间。
T3:Sanrd
这个题等价于求[l,r]区间内次大质因子的和。
50分给了埃氏筛法：先筛出sqrt(r)内的质数，然后枚举质因子，从ceil(l/p)*p枚举到floor(r/p)*p,总复杂度为[l,r]内质因子个数，即(r-l)*log(r).
然后就是可怕的数论了：（好吧，这个题推失败了，先弃坑）
定义f[i]为乘积为i的数的最大质因子之和。$
$小到大枚举质因子的话就能保证最后一次转移前的f[i]是次大质因子。$
$对于一个数，它的次大质因子一定<\sqrt n，所以对于>=\sqrt n的质因子我们一起转移。$
$对于一个已知的f[i],还能转移的因子一定满足<=\lfloor\frac{n}{i}\rfloor$
$设g[x]=\sum_{\lfloor\frac{n}{i}\rfloor==x}{f[i]}$
$现在问题可以分成两类：$
$1、求>=\lfloor\frac{n}{i}\rfloor==x且<=\sqrt n 的质数个数$
$2、用<=\sqrt n 的质数完成g[i]的转移$
$对于第一部分：设g[i][j]表示考虑前i个质数1到j中与之互质数的个数$
$g[i][j]=g[i-1][j]-g[i-1][\lfloor\frac{j}{prime[i]}\rfloor]
UR #14:
T1：最强跳蚤
我果然是太菜了，连T1都不会。除了暴力只想到了w<=80的另外10分做法：启发式合并装着用LL状压质因子出现次数奇偶性的数组，复杂度O(nlogn).
正解的随机化算法昨天考试刚刚见到，但是我没改那道题，果然印象不深啊：给每一个质数随即一个2^64以内的权值，一个数的权值等于所有质因子权值的异或和，那么一条路径权值乘积为完全平方数的条件可以近似等价于异或和为零。我们甚至可以不用树分治，因为两条路径的异或值等于它们到根的异或值的异或（点权的话还等考虑lca的权值），这样这道题只需要分解因数+排序就可以完成了，复杂度O(nlogn).
T2：人类补完计划
这个题可能先枚举点集，再枚举闭合子图中的边的话复杂度会玄学一点，能得多少分就不知道了。。
最不会这种生成个***的计数问题了。。这个题是个带权的基环树计数，权值为2^w(w为基环树中非叶节点的个数）。然后，先弃坑吧。。
T3：思考熊
只会20分暴力分：即用st表O(1)查询lca做到O(nm)。
我居然忘记了没有删除操作怎么做！这可是我当时在某次考试时自己想出来！就是对于对于可能的询问分个块，用bfs预处理出来这个块内的点到达树上其他所有点的距离最大值，使用树形DP解决，这样的话空间和时间都是O(nsqrt(n))的。
对于这道题：可以用来写40分做法：设置一个块的大小，然后一个块满了就跑一遍bfs，这样做可以被卡：在一个块快满的地方反复的插入和删除。但是出题人非常良心，说了：我不知道泥萌块的大小，而且随机一个块的大小我更卡不掉了。所以就给过了40分。（假如不是捆绑就可以得好多分了。）
咦？这个虽然强制在线但是我们还是知道哪次操作是插入，哪次是删除，那我们是不是可以离线调整块的大小？（有待尝试）
后来看完了题解，题解给出了这样一种维护方式：在删除涉及的块（最后一个块）打上标记，表示这个块信息不对，当查询时若一个块带标记，那么就暴力。在插入的时候如果一个块满了，那么看一下前一个块，假如前一个块有标记，就重构前一个块，否则什么也不做。这样做保证了查询时只可能有一个块打上了标记（但是在非查询时刻可能有多个），所以复杂度保证了O(nsqrt(n)),但是nsqrt(n)的空间复杂度难以接受。
对于第五个子任务w>=0,我们可以维护直径：用一个线段树维护一个我们询问队列的区间中点集的直径的两端点，可以支持合并删除、插入，查询的时候就查找对应区间的端点然后更新距离最大值就行了。
对于有负权的，树的直径的理论不成立了。我们用虚树处理出虚树上每个点离他最远的黑点，这样查询时只要找到他所在的边上，就可以得到最远的黑点的距离了。我们使用二进制分组来处理插入和撤销：二进制分组使得块形成了线段树结构，这样查询的时候就可以分log棵虚树，每个虚树花费log的时间，复杂度是nlog^2的。再来考虑删除，仍像分块一样给最后的块（最多log个）打标记，然后查询的时候如果有标记就递归，然后当一块满的时候如果前一块有标记，就重建，否则什么也不做，这样就保证了nlog^2的复杂度和nlog的空间了！
UNR #1 Day1:
T1:争夺圣杯
这个题还是比较像T1的，我们考虑一个i的贡献：先求出向左向右延伸长度，为了防止重复，一个取等一个不取等，假设向左延伸长度为L，向右为R，枚举左边的长度，发现给长度为i的贡献key=a[i]的规律为:1~R,2~R+1,3~R+2,...L~R+L-1,然后发现对于1~L贡献为i*key,对于L+1~R贡献为L*key,对于R+1~R+L-1贡献为L-(i-R)*key=(L+R-i)*key,这样的话用个差分数组就可以O(n)求解了。
坑点：使用加减法来取膜时，要注意读入的数如果比模数大，那么两个数的和减一次模数就不够了。而且读入后由于需要用到它的值来比较，所以必须比较完了再取膜。
T2:合唱队形
对于n==m的情况，每个人必须学会的音固定，设共有tot门课程,f[i]为还差i门课的期望，f[i]=f[i]*(tot-i)/tot+f[i-1]*i/tot+1,移项得f[i]=f[i-1]+tot/i,边界f[0]=0,所以ans=f[m]=sum{tot/i}
对于n,m<=5,ti<=3的情况，可以发现状态数<=2^(3*5),可以状压计算到达每个状态的期望，除了自环以外这是一个DAG，拓扑一下就可以转移了，转移到一个点，解一下自己的方程就行了。
然后就不会了，去看题解：
对于m<=n/2即m<=15的情况可以状压m：因为只有m个与第i个人有关，所以只状压这m个即可。定义f[i][S]为到第i个人，以他为尾的串匹配状态，然后大力转移。
对于m> n/2的状态我们可以容斥,我们设f[t]为在t时刻未终止的概率，则2^(n-m)枚举一下哪些位置为起点的完成匹配，容斥一下,p[S]为在t时刻S集未完成的概率，g[S]表示有S内的任务需要的完成次数的期望，设为了完成S集合的匹配，需要学习的集合为K[S],则
$g[S]=\sum_{i=1}^{k}tot/i$
$Ans=\sum_{t=0}^{oo}\sum_{S}(-1)^{|S|}*(1-p[S])$
$Ans=\sum_{S}(-1)^{|S|}*1-\sum_{S}(-1)^{|S|}\sum_{t=0}^{oo}p[S]$
$Ans=-\sum_{S}(-1)^{|S|}\sum_{t=0}^{oo}p[S]$
$Ans=-\sum_{S}(-1)^{|S|}g[S]/tot$(tot相当于权值)
$Ans=-\sum_{S}(-1)^{|S|}\sum_{i=1}^{K[S]}1/i$
T3:果冻运输
手残党手玩也不会，爆搜也不会。。有机会像猫老师一样改checker试试。
UNR #1 Day2:
T1:Jakarta Skyscrapers
又是良心题，可以知道c>max(a,b)和c不是gcd(a,b)倍数时无解，其他时候有解，考虑怎么求gcd，更相减损术是没有复杂度保证的，但我们可以这样“倍增”：由(a,b)的到b-a,由(a,b-a)得到b-2a,由(b-2a,b)得到2a。这样我们先得到gcd，再用同样的方法倍增得到c。
T2:奇怪的线段树
可以发现无解的情况是一个点是白的但他的子树中有黑的。同时发现如果一个点子树中有黑的，那么这个点没有存在的必要，因为只要将它子树中的点染黑，就一定会把它染黑。这显然是一个覆盖点的最小路径覆盖，可以使用有下界的最小流来写，然后考虑到一个操作[s,t]肯定是从左到右先上去再下来，过程中可能有分叉，当我们去除掉所有没用的节点后一定是从左到右对应一坨右儿子然后接一坨左儿子，而一个右儿子i可能的后继j满足l[j]=r[i]+1,一个左儿子可能的后继也满足l[j]=r[i]+1,同时j是一个左儿子，否则不合法。这样直接建边的话边数是n^2的，考虑如何优化：新建n个节点，对于右儿子，向ri+1连边，从li连来边，对于左儿子，从li连来边，同时仍然向满足l[j]=r[i]+1的左儿子连边（这种点只有一个）。这样边数就降到了O(n)，就可以过了。
T3:火车管理
没时间了，先弃吧。
UR #15:
T1:奥林匹克五子棋
这个题也是秀一秀智商。当k<=2时，一定无解，当k>=3时，完全可以把k当成3来构造。当k等于3时，可以构造类似于：
0101
0101
1010
1010
用这种东西就可以安全的填满n*m的格子了。
T2:奥林匹克环城马拉松
来不及填了，就弃坑吧。
T3:奥林匹克数据结构
来不及填了，就弃坑吧。
UR #16:
T1:破坏发射台
这个题还是略有难度的，对于n为奇数，不存在相对的情况，所以可以这样，设1号的颜色为A，然后用f[i][01]表示i与1的颜色是否相同，这样转移就显然了，可以用矩阵加速。
对于n为偶数，存在相对的情况，这个时候就可以设1号颜色为A，i+n/2号颜色为B，用f[i][012][012]表示i的颜色是否为A或者B和i+n/2的颜色是否为A或者B，然后大力转移就好了。
T2:破坏蛋糕
来不及填了，就弃坑吧。
T3:破坏导蛋
来不及填了，就弃坑吧。
UNR #2 Day1:
T1：UOJ拯救计划
这题一上来发现答案膜6，真是奇怪，一定有蹊跷，但是一时没看出来。又过了一会，似乎发现了个规律？！赶紧写个交上去，然后写个暴力对拍一下，发现有反例，然后就修，修完还能拍出反例，就接着改。。不知不觉的一个半小时过去了。。这时候才意识到这样子做下去是没有前途的，所以开始换思路，其间想到了包括求出mod2和mod3的答案再CRT合并了等等，各种奇葩思路，后来突然想到：使用3种即3种以上颜色染色的方案一定可以乘一个A(k,3)，A(k,3)=C(k,3)*A(3,3)=C(k,3)*6,一旦mod6就成零了！好了，接下来这样将它二分图染色，并单独处理单个点的，最后每个联通块的答案乘在一起就行了。写完后感觉边界有点多，就先对拍，结果忘记交了。。直到T2想完了才想起来没交呢。。
T2：排兵布阵
一开始的时候数据范围看跑了，以为能量的增加量可能也有负的，这样直接所有算法多个log，后来才发现没有负的，这样就不需要堆或者set了。
这个题虽然想到了n*sqrt(nlog)的做法，但是十分担心会常数狗带，加上没时间了，就没去写，分别把3种暴力写了。
对于没有移动的：我们发现长度>sqrt(n)的不超过sqrt(n)个，所以分情况讨论一下，修改时把长的打个标记，短的暴力修改，查询的时候看一看长的和本行（列）的交点更新答案就行了，记得去重！！不去重的话会出现：行和列交点存在多个点，这样的话复杂度就不对辣！
对于没有修改的，直接用map存一下，移动的时候合并一下就行了。
对于所有操作都有的，可以先分个块，然后移动的时候看能不能合并，能的话启发式合并一下，复杂度就成了O(n*sqrt(nlog)).
然后看了看题解，果然我太naive,题解复杂度是O(nsqrt(n))的。
题解的分块方法比我高到不知道哪里去了！是这样的：一个点是他所在行和列中点数较小的那个的关键点，这样的话每一行和列的关键点数是不超过sqrt(n)的，修改的时候暴力修改关键点，然后打个标记。移动的时候，如果不需要合并的话什么事也没有，合并的话我们需要做三件事（假如当前是合并行）：有的关键点变成列的了，之中因为只有sqrt(n)个，所以可以暴力。合并标记，这一步不能暴力，因为非行关键点数量是比较多的，可以这样做：用一个并查集维护标记差。去重点：这一步题解给出了极妙的做法：设一个值1.5*sqrt(n)左右，每次暴力时看看关键点数量是否超过这个值，如果超过，就去重，因为去重后点就不见了，所以这一步的复杂度是单出来的，所以可以用map维护，这样的话每次去至少0.5sqrt(n),复杂度累赘也最多为0.5sqrt(n),去重的复杂度就是单出来的nlogn.这样的话总体的复杂度就是O(nsqrt(n)+nlog(n))的了。
实践的时候因为行列的操作相同，所以我用了一个结构体使得行列唯一的不同体现在传的参数bool型的b上，这样虽然代码长度虽然理论上短了一半，但是代码长度的常数增大了，所以实际效果大概是短了1/3，同时这样做可能会发生一些鬼畜的事情。
注意：这道题告诉我，map中的东西假如被赋上一个值，然后erase掉，然后再直接访问，你会发现它的值不是0！而是之前被赋的值！
T3：黎明前的巧克力
T2写了60以后开始吃饭，吃饭花了30分钟就到了12:50了，先写个3^n*n暴力去，写的时候发现话2^n*n预处理之后就变成玄学3^n的了，然而没什么O用，还是5分。
这时候发现T2有大样例而且没过！（QAQ平时考试几乎从来没有大样例，而且看T1没大样例以为都没有呢）赶紧下下来找错误，妈呀，暴力都错了！可是我和其他两个部分分拍过了啊！那是不是说明我读错题了！？惨啊，还剩20分钟，就开始读代码，读了几分钟看了个遍也没发现问题，又去看题意，确定没读错题，完蛋了，只剩10分钟了，T2要爆零了！
突然，我发现我所有的负数都错了，可是我考虑负数了啊！难道是...没错，快读写错了！（叫你平时懒，写快读只写读非负数的！）
这样就没时间想T3了。。
事后想了一下，大概有这么一点思路：如果一个集合异或值为0，那么只需要从中任取一个集合，然后取它的补集就行，这样一个大小为S的集合，对答案贡献是2^S,所以问题等价成了有多少个大小为i的集合异或值为0。
考虑DP：定义f[i][S]为考虑前i个数，异或和为S的贡献，f[0][0]=1,f[i][S^a[i]]=f[i-1][S^a[i]](不选)+f[i-1][S]*2(选，贡献为二的幂次加1).复杂度n*2^m,可以得到30分。
对于不同数字较少的特殊数据，因为两个一样的数字异或起来为0，所以只需要讨论每种数出现的奇偶性，f[i][S^a[i]]=f[i-1][S^a[i]]*g[i][0]+f[i-1][S]*g[i][1]，可以多得10分，而且这个算法可以直接得40分。
再从FWT角度考虑之前的DP:f[i][S^a[i]]=f[i-1][S^a[i]]+f[i-1][S]*2,相当于是将第i个转移多项式的a[i]处放上2,在0处放上1，然后卷在一起。我们可以将所有的转移都DFT出来，然后乘在一起，最后IDFT回去,f[0]就成为了答案，但是复杂度n*2^m*m，但是出题人比较有趣，然这个算法爆零。
我们考虑，假设DFT后某个位置上有x个贡献-1，那么有n-x个贡献3，那么这个位置的和为s=3(n-x)-x,假如我们知道了这个s，我们可以推出x=(3n-s)/4,那么这个位置的应有值(-1)^x*3^(n-x)就可以计算了。又由于FWT(A+B)=FWT(A)+FWT(B)，所以只要将所有数的DFT之前的加在一起，然后DFT一下，我们就有了s,然后求出x顺理成章可以得到x和(-1)^x*3^(n-x)，接下来就可以IDFT回去，就得到我们想要的答案了！
UNR #2 Day2:
这场比赛滚大cu了。一开始T1看错题，把乘看成了加，然后思考一会出了n^3做法，然后就写，写完后过了样例1，却过不了样例2，然后就开始调啊调，直到我把样例二n^3模拟了一遍，觉得自己程序和自己模拟的一样啊？！然后重新读了一遍题，发现自己读错题了，然而已经10点多了，然后心态爆炸，想了想只想出一个n^5的，然后转移倍恶心，一看只能过n<=15不如去写个n^2*2^n的，然而意识到似乎可以n*2^n？因为样例3中n=20，加上之前看错题耽误太长时间心情不好，所以不想写n^2*n^2,就去写n*2^n的，结果又是一直有一些状态重复（如(1,1)被算两次），然后心态越来越差，一看过去了3个半小时了，决定弃疗，写个n^2*2^n的，迅速过掉样例（自己作死非要跟自己较真），然后读了读T2感觉只会10分，就瞎xx写了一个，然后因为没取膜爆了零，接下来去写T3，本来就不会提答，剩下一个小时怎么玩！？看看点一二还是比较简单的，又看见点七分比较少，就去开点七，看起来是棵树，就又开始做死，写树上建PAM（即支持撤销的PAM）可复杂度还是n^2的。。最后就只有这三个点的分，然后就滚大cu了。。
这次滚cu完全是因为自己作死，读错题+跟自己较真+忘取膜+提答不观察所有数据（话说最后一个点那么大，notepad++都打不开，但是meaty说暴力能过？）
T1：积劳成疾
本题都是利用期望的线性性计算（因为以终态为初始状态的话dp值未知）
n^2*2^n的做法：考虑从大到小插入数，然后显然覆盖到已插入位置的k长度集合一定贡献已经确定，所以我们可以n*2^n预处理出S集合中i位前第一个和后第一个为1的数的位置，然后从大到小枚举i，定义f[S]为S集合已有数的期望，这样只需要考虑插入一个数后会有多少个k长线段以i为最大值，这个显然是可以利用我们预处理的东西O(1)计算的，设有v个，f[S]*Pow(w[i],v)->f[S|(1<<j)].这样要注意枚举顺序：为了保证(i,i)的不会被计算多次，所以要先从小到大枚举j,然后枚举S，这样利用了完全背包的性质，可以保证既不重又不会漏。可以得到40分。
然后对于k==1 的，f[i]=f[i-1]*sum.
对于k==2的，定义f[i][j]为第i位为j的期望，可以转移f[i-1][j]*w[max(j,k)]->f[i][k],复杂度n^3,可以得到15分。
看了正解，发现自己真是naive的很啊！考场上明明深入对着按照i覆盖的区间把贡献考虑了半天，但是仍然没有做出来。
这样定义状态：f[i][j]为使用的最大值<=i的长度为j的区间的期望。则对于j<k有f[i][j]=Pow(i,j),对于j>=k有f[i][j]=f[i-1][j]+sum{f[i-1][p-1]*f[i][j-p]*Pow(w[i],len)}.len为i放在p处时的贡献的k长线段的个数。什么，你说会重复计数？不会的，因为你使用的p-1长度和j-p长度内当然没有将两个序列连接起来位置的贡献了。这样做复杂度n^3.
T2：梦中的题面
来不及改了，先弃坑。
T3：解开尘封的仪式
听说这个题除了2和3都可以暴力搞。
先判了判发现1、7、9都是树，就写了个树上PAM（即带撤销的），第9个点开不下数组，然后Meaty告诉我字符集只有4（我打不开第九个点啊！），然后开下了数组，结果开了栈还爆栈，听Meaty开了512M的栈，然后跑不出，想起来撤销复杂度不对，所以加了个Trie图优化，这样复杂度是n*4的，讲道理1s内应该可以跑出来，可是光读入就好几秒，加上太耗内存，还是跑了许久。
接下来看点2，发现字符都一样，所以直接输出最长链（记忆化DP）。然后看点3，发现是一群“菱形”连在一起，这个只需要使用manacher在比较时比较4对就可以了。
然后看点4，发现先是一棵树，然后又是一棵树，然后是一堆奇怪的东西，用第二个点的程序算出来最大深度只有19，就试了试爆搜，结果秒过了。想接着爆搜试试，看了看5、6、8的最大深度分别为不到6W、33、3601，结果除了第6个点都跑出来了，看来5和8分叉比较少。
现在只剩第6个点了。发现有不少重边，于是去了下重边，然而还是有很多边，跑了大概2分钟跑了出来。
可以说这个题答题可能是由于出题人良心减小数据范围而变水了。
鄂公网安备 42010202000505 号